{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Distance Value Between Two Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findTheDistanceValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个数组间的距离值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数数组&nbsp;<code>arr1</code>&nbsp;，&nbsp;<code>arr2</code>&nbsp;和一个整数&nbsp;<code>d</code>&nbsp;，请你返回两个数组之间的&nbsp;<strong>距离值</strong>&nbsp;。</p>\n",
    "\n",
    "<p>「<strong>距离值</strong>」<strong>&nbsp;</strong>定义为符合此距离要求的元素数目：对于元素&nbsp;<code>arr1[i]</code>&nbsp;，不存在任何元素&nbsp;<code>arr2[j]</code>&nbsp;满足 <code>|arr1[i]-arr2[j]| &lt;= d</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "对于 arr1[0]=4 我们有：\n",
    "|4-10|=6 &gt; d=2 \n",
    "|4-9|=5 &gt; d=2 \n",
    "|4-1|=3 &gt; d=2 \n",
    "|4-8|=4 &gt; d=2 \n",
    "所以 arr1[0]=4 符合距离要求\n",
    "\n",
    "对于 arr1[1]=5 我们有：\n",
    "|5-10|=5 &gt; d=2 \n",
    "|5-9|=4 &gt; d=2 \n",
    "|5-1|=4 &gt; d=2 \n",
    "|5-8|=3 &gt; d=2\n",
    "所以 arr1[1]=5 也符合距离要求\n",
    "\n",
    "对于 arr1[2]=8 我们有：\n",
    "<strong>|8-10|=2 &lt;= d=2</strong>\n",
    "<strong>|8-9|=1 &lt;= d=2</strong>\n",
    "|8-1|=7 &gt; d=2\n",
    "<strong>|8-8|=0 &lt;= d=2</strong>\n",
    "存在距离小于等于 2 的情况，不符合距离要求 \n",
    "\n",
    "故而只有 arr1[0]=4 和 arr1[1]=5 两个符合距离要求，距离值为 2</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr1.length, arr2.length &lt;= 500</code></li>\n",
    "\t<li><code>-10^3 &lt;= arr1[i], arr2[j] &lt;= 10^3</code></li>\n",
    "\t<li><code>0 &lt;= d &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-distance-value-between-two-arrays](https://leetcode.cn/problems/find-the-distance-value-between-two-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-distance-value-between-two-arrays](https://leetcode.cn/problems/find-the-distance-value-between-two-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,5,8]\\n[10,9,1,8]\\n2', '[1,4,2,3]\\n[-4,-3,6,10,20,30]\\n3', '[2,1,100,3]\\n[-5,-2,10,-3,7]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        s = 0\n",
    "        for i in arr1:\n",
    "            result = True\n",
    "            for n in arr2:\n",
    "                if i>n and i-n>d:\n",
    "                    continue\n",
    "                elif i<n and n-i>d:\n",
    "                    continue\n",
    "                else:\n",
    "                    result = False\n",
    "                    break\n",
    "            if result == True:\n",
    "                s += 1\n",
    "        return s\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        ans=0\n",
    "        for i in arr1:\n",
    "            if all(abs(i-y)>d for y in arr2):\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        c = 0\n",
    "        for i in arr1:\n",
    "            for j in arr2:\n",
    "                if abs(i - j) <= d:\n",
    "                    break\n",
    "            else:\n",
    "                c += 1\n",
    "        \n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        counter=dict()\n",
    "        for i in range(len(arr1)):\n",
    "            counter[arr1[i]]=0\n",
    "        for i in range(len(arr1)):\n",
    "            for j in range(len(arr2)):\n",
    "                if abs(arr2[j]-arr1[i])<=d:\n",
    "                    counter[arr1[i]]+=1\n",
    "        ans=0\n",
    "        for i in range(len(arr1)):\n",
    "            if counter[arr1[i]]==0:\n",
    "                ans+=1\n",
    "        return ans\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        ans = 0\n",
    "        for a in arr1:\n",
    "            f = True\n",
    "            for b in arr2:\n",
    "                if abs(a - b) <= d:\n",
    "                    f = False\n",
    "                    break\n",
    "            if f:\n",
    "                ans += 1\n",
    "        return  ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        res = 0\n",
    "        for i in arr1:\n",
    "            found = True  # 在外部循环内初始化为True\n",
    "            for j in arr2:\n",
    "                if abs(i - j) <= d:\n",
    "                    found = False\n",
    "                    break\n",
    "            if found:\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        ans = 0\n",
    "        for n1 in arr1:\n",
    "            bools = [int(abs(n1 - i) <= d) for i in arr2]\n",
    "            if sum(bools) == 0:\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        \"\"\"\n",
    "        对于arr1中的任意一个元素x1和arr2中元素x2，则有|x1 - x2| <= d --> x2应该在[x1-d, x1+d]之间\n",
    "        也就是对于arr1中的x1，如果arr2中存在任意x2在[x1-d, d+x1]之间，这个x1就不满足条件\n",
    "        我们可以先对arr2进行排序，让蓝色区域为x2<x1-d，最后left就是最后一个x2小于x1-d的【target就是x1-d】\n",
    "        那如果x1满足条件，left+1对应的x2就应该大于d+x1【当然如果left已经是最后一个x2，就不用排序了】\n",
    "\n",
    "        整体上对arr1中元素进行遍历，分别判断每个元素是否满足条件\n",
    "        \"\"\"\n",
    "        arr2.sort()\n",
    "        res = 0\n",
    "        for value in arr1:\n",
    "            left = self.get_left(arr2, value-d)\n",
    "            if left==len(arr2)-1 or arr2[left+1]>value+d:\n",
    "                res += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "    def get_left(self, nums, target):\n",
    "        left, right = -1, len(nums)\n",
    "        while left+1 < right:\n",
    "            mid = (left+right)>>1\n",
    "            if nums[mid]<target:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        n = len(arr2)\n",
    "        arr2.sort()     \n",
    "        def check(v):\n",
    "            left, right = 0, n\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if abs(arr2[mid] - v) <= d:\n",
    "                    return False\n",
    "                elif arr2[mid] > v:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return True\n",
    "\n",
    "        return sum(check(v) for v in arr1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        count =0\n",
    "        for x in arr1:\n",
    "            if all(abs(x - y) > d for y in arr2):\n",
    "                count +=1\n",
    "        return count\n",
    "\n",
    "                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        cnt = len(arr1)\n",
    "        for a1 in arr1:\n",
    "            for a2 in arr2:\n",
    "                if abs(a1-a2) <= d:\n",
    "                    cnt -= 1\n",
    "                    break\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        res=len(arr1)\n",
    "        arr2.sort()\n",
    "        # for aa in arr1:\n",
    "        #     index1=bisect_left(arr2,aa-d)\n",
    "        #     index2=bisect.bisect(arr2,aa+d)\n",
    "        #     if index1==index2:\n",
    "        #         res+=1\n",
    "        # return res\n",
    "        for i in range(len(arr1)):\n",
    "            left=0\n",
    "            right=len(arr2)-1\n",
    "            while left<=right:\n",
    "                mid=(left+right)//2\n",
    "                if abs(arr2[mid]-arr1[i])<=d:\n",
    "                    res-=1\n",
    "                    break\n",
    "                else:\n",
    "                    if arr1[i]-arr2[mid]<0:\n",
    "                        right=mid-1\n",
    "                    else:\n",
    "                        left=mid+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        ans = 0\n",
    "        for x in arr1:\n",
    "            flag = True\n",
    "            for y in arr2:\n",
    "                if abs(x - y) <= d:\n",
    "                    flag = not flag\n",
    "                    break\n",
    "            if flag:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(arr1)):\n",
    "            temp = 0\n",
    "            for j in range(len(arr2)):\n",
    "                if abs(arr1[i] - arr2[j]) <=d:\n",
    "                    temp =1\n",
    "                    break\n",
    "            if temp == 0:\n",
    "                ans +=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        \n",
    "        num = 0\n",
    "        for i in arr1:\n",
    "            target = all(abs(i-j) > d for j in arr2)\n",
    "            if target :\n",
    "                num += 1\n",
    "        return num\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        _sum = 0\n",
    "        for i in range(0, len(arr1)):\n",
    "            _continue = None\n",
    "            for j in range(0, len(arr2)):\n",
    "                if abs(arr1[i] - arr2[j]) <= d:\n",
    "                    _continue = True\n",
    "                    break\n",
    "            if not _continue:\n",
    "                _sum += 1\n",
    "        return _sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        b=0\n",
    "        for i in arr1:\n",
    "            a=0\n",
    "            for j in arr2:\n",
    "                if abs(i-j)<=d:\n",
    "                    a=1\n",
    "                    break\n",
    "            if a==0:\n",
    "                b+=1\n",
    "        return b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        ans = 0\n",
    "        for i in arr1:\n",
    "            for j in arr2:\n",
    "                if abs(i-j) <= d:\n",
    "                    break\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "\n",
    "        # 暴力+排序\n",
    "        # arr1.sort()\n",
    "        # arr2.sort()\n",
    "        # n = len(arr2)\n",
    "        # ans = 0\n",
    "        # for nu in arr1:\n",
    "        #     flag = True\n",
    "        #     for i in range(n):\n",
    "        #         if abs(nu-arr2[i]) <= d:\n",
    "        #             flag = False\n",
    "        #             continue\n",
    "        #     if flag:\n",
    "        #         ans += 1\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        # 区间二分查找:对选定的arr1元素x，如能在[x-d, x+d]区间找到一个arr2元素，则不符合。\n",
    "        import bisect\n",
    "        arr2.sort()\n",
    "        ans = 0 \n",
    "        for nu in arr1:\n",
    "            i = bisect.bisect_left(arr2, nu-d) # 找x-d的左边界\n",
    "            j = bisect.bisect_right(arr2, nu+d) # x+d的右边界\n",
    "            if i == j: # 左==右，说明[x-d, x+d]区间找不到.\n",
    "                # print(i, j)\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        arr2.sort()\n",
    "        res = 0\n",
    "        lenth = len(arr2)\n",
    "        for n in arr1:\n",
    "            i = bisect_right(arr2, n)\n",
    "            if i >= lenth:\n",
    "                dis = abs(arr2[i-1]-n)\n",
    "            else:\n",
    "                dis = min(abs(arr2[i]-n), abs(arr2[i-1]-n))\n",
    "            if dis > d:\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        ans=0\n",
    "        for i in arr1:\n",
    "            for j in arr2:\n",
    "                if abs(i-j)<=d:\n",
    "                    break\n",
    "            else:\n",
    "                ans+=1\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        arr1.sort()\n",
    "        arr2.sort()\n",
    "        left = right = 0\n",
    "        res = 0\n",
    "        for i in arr1:\n",
    "            while left < len(arr2) and arr2[left] + d < i:\n",
    "                left += 1\n",
    "            # right = left\n",
    "            while right < len(arr2) and arr2[right] - d <= i:\n",
    "                right += 1\n",
    "            if left == right:\n",
    "                res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "\n",
    "        cnt = 0\n",
    "        for x in arr1:\n",
    "            if all(abs(x-y) > d for y in arr2):\n",
    "                cnt += 1\n",
    "        \n",
    "        return cnt\n",
    "\n",
    "        # l1 = len(arr1)\n",
    "        # l2 = len(arr2)\n",
    "        # dist = 0\n",
    "        # count = 0\n",
    "        # for i in range(l1):\n",
    "        #     j = 0\n",
    "        #     while j < l2:\n",
    "        #         if abs(arr1[i] - arr2[j]) <= d:\n",
    "        #             break\n",
    "        #         else:\n",
    "        #             j += 1\n",
    "\n",
    "        #     if j == l2:\n",
    "        #         count += 1\n",
    "        \n",
    "        # return count\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        res = []\n",
    "        for a1 in arr1:\n",
    "            flag = True\n",
    "            for a2 in arr2:\n",
    "                if abs(a1-a2)<=d: flag=False\n",
    "            if flag:res.append(a1)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        c=0\n",
    "        for i in arr1:\n",
    "            for j in arr2:\n",
    "                if abs(i-j)<=d:\n",
    "                    c+=1\n",
    "                    break\n",
    "        return len(arr1)-c\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        return sum(all(abs(v1 - v2) > d for v2 in arr2) for v1 in arr1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        count = 0\n",
    "        for x in arr1:\n",
    "            if all(abs(x - y) > d for y in arr2): count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        ans = len(arr1)\n",
    "        for i in arr1:\n",
    "            for j in arr2:\n",
    "                if abs(i - j) <= d:\n",
    "                    ans -= 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        arr2.sort()\n",
    "        n = len(arr2)\n",
    "        ans = 0\n",
    "        for i in arr1:\n",
    "            if i <= arr2[0]:\n",
    "                if abs(i-arr2[0])>d:\n",
    "                    ans += 1\n",
    "                    continue\n",
    "            elif i >= arr2[-1]:\n",
    "                if abs(i-arr2[-1]) > d:\n",
    "                    ans += 1\n",
    "                    continue\n",
    "            else:\n",
    "                for j in range(0,n-1):\n",
    "                    if arr2[j] <= i and arr2[j+1] >= i:\n",
    "                        if abs(i-arr2[j]) > d and abs(i-arr2[j+1]) > d:\n",
    "                            ans += 1\n",
    "                            break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        ans = 0\n",
    "        arr2.sort()\n",
    "        def bisearch(arr, low, high):\n",
    "            l, r = 0, len(arr)\n",
    "            while l < r:\n",
    "                mid = (l+r) // 2\n",
    "                if low <= arr[mid] <= high:\n",
    "                    return True\n",
    "                elif arr[mid] > low:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid+1\n",
    "            return False\n",
    "        # 对arr2二分查找，如果找到在x-d, x+d的数则不满足条件\n",
    "        for a in arr1:\n",
    "            low = a - d\n",
    "            high = a + d\n",
    "            if not bisearch(arr2, low, high):\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        arr2.sort(reverse=True)\n",
    "        ans = 0\n",
    "        for a1 in arr1:\n",
    "            flag = True\n",
    "            for a2 in arr2:\n",
    "                if abs(a1 - a2) <= d:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        res = 0\n",
    "        arr2.sort()\n",
    "        for a1 in arr1:\n",
    "            flag=True\n",
    "            left,right=0,len(arr2)-1\n",
    "            #print(a1,arr2,d)\n",
    "            while left<=right:\n",
    "                p = left+(right-left)//2\n",
    "                #print('1:',a1,arr2[p],left,p,right)\n",
    "                if d>=abs(a1-arr2[p]):\n",
    "                    flag=False\n",
    "                    #print('False')\n",
    "                    break\n",
    "                elif arr2[p]>a1+d:right=p-1\n",
    "                elif arr2[p]<a1-d:left=p+1\n",
    "\n",
    "            if flag:res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        sorted(arr1)\n",
    "        sorted(arr2,reverse = True)\n",
    "        ans = 0\n",
    "        for i in arr1:\n",
    "            for j in arr2:\n",
    "                if abs(i-j) <= d:\n",
    "                    ans +=1\n",
    "                    break\n",
    "        return len(arr1) - ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        count = 0\n",
    "        arr2.sort()\n",
    "        for x in arr1:\n",
    "            p = bisect.bisect_left(arr2,x)\n",
    "            if p == len(arr2) or abs(x - arr2[p]) > d:\n",
    "                if abs(x - arr2[p - 1]) > d or p == 0:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        ans = 0\n",
    "        for num in arr1:\n",
    "            flag = 1\n",
    "            for number in arr2:\n",
    "                if abs(number-num) <= d:\n",
    "                    flag = 0\n",
    "                    break\n",
    "            if flag:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(len(arr1)):\n",
    "            count1 = 0\n",
    "            for  j in range(len(arr2)):\n",
    "                if abs(arr1[i] - arr2[j]) > d:\n",
    "                    count1 += 1\n",
    "\n",
    "            if count1 == len(arr2):\n",
    "                count += 1\n",
    "                \n",
    "        return count\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(0, len(arr1)):\n",
    "            jd = True\n",
    "            for j in range(0, len(arr2)):\n",
    "                if abs(arr1[i] - arr2[j]) > d:\n",
    "                    continue\n",
    "                else:\n",
    "                    jd = False\n",
    "                    break\n",
    "            if jd:\n",
    "                res = res + 1 \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        res=0\n",
    "        for i in arr1:\n",
    "            f=True\n",
    "            for j in arr2:\n",
    "                if i-d<=j<=i+d:\n",
    "                    f=False\n",
    "                    break\n",
    "            if f==True:\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        count = 0\n",
    "        for i in arr1:\n",
    "            flag = True\n",
    "            for j in arr2:\n",
    "                if abs(i - j) <= d:\n",
    "                    flag =False\n",
    "                    break\n",
    "            if flag == True:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        arr2.sort()\n",
    "        cnt = 0\n",
    "        for x in arr1:\n",
    "            p = bisect.bisect_left(arr2,x)\n",
    "            if p==len(arr2) or abs(x - arr2[p]) > d:\n",
    "                if p == 0 or abs(x - arr2[p-1]) > d:\n",
    "                    cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        arr2.sort()\n",
    "        cnt = 0\n",
    "        for x in arr1:\n",
    "            p = bisect.bisect_left(arr2, x)\n",
    "            if p == len(arr2) or abs(x - arr2[p]) > d:\n",
    "                if p == 0 or abs(x - arr2[p - 1]) > d:\n",
    "                    cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        arr2.sort()\n",
    "        num = 0 \n",
    "        for i in arr1:\n",
    "            index = bisect.bisect_left(arr2, i)\n",
    "            if index == 0:\n",
    "                if abs(arr2[index]-i) > d :\n",
    "                    num += 1\n",
    "            elif index == len(arr2):\n",
    "                if abs(arr2[-1]-i) > d :\n",
    "                    num += 1\n",
    "            else:\n",
    "                if (abs(arr2[index]-i) > d) and (abs(arr2[index-1]-i) > d):\n",
    "                    num += 1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        count = 0\n",
    "        for i in arr1:\n",
    "            temp = 0\n",
    "            for j in arr2:\n",
    "                if abs(i-j)<=d:\n",
    "                    temp = 1\n",
    "                    break\n",
    "            if temp==1:\n",
    "                continue\n",
    "            count = count+1\n",
    "        return count\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        count = 0\n",
    "        for x in arr1:\n",
    "            arr2_num = 0\n",
    "            for y in arr2:\n",
    "                arr2_num += 1\n",
    "                if abs(x-y) <= d: break\n",
    "                if arr2_num == len(arr2) and abs(x-y) > d: count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: list[int], arr2: list[int], d: int) -> int:\n",
    "        ans = 0\n",
    "        for a in arr1:\n",
    "            arr2.append(a)\n",
    "            arr2.sort()\n",
    "            if arr2[0] == a:\n",
    "                if abs(a - arr2[1]) > d:\n",
    "                    ans += 1\n",
    "            elif arr2[-1] == a:\n",
    "                if abs(a - arr2[-2]) > d:\n",
    "                    ans += 1\n",
    "            else:\n",
    "                i = arr2.index(a)\n",
    "                if abs(a - arr2[i - 1]) > d and abs(a - arr2[i + 1]) > d:\n",
    "                    ans += 1\n",
    "            arr2.remove(a)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        length = len(arr2)\n",
    "\n",
    "        count = 0\n",
    "        for num in arr1:\n",
    "            idx = 0\n",
    "            while idx < length:\n",
    "                if abs(num - arr2[idx]) > d:\n",
    "                    idx += 1\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                count += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        count=0\n",
    "        for i in arr1:\n",
    "            dis=0\n",
    "            for j in arr2:\n",
    "                if abs(i-j)<=d:\n",
    "                    dis+=1\n",
    "                    break\n",
    "            if dis==0:\n",
    "                count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        arr2.sort(reverse=True)\n",
    "        res = 0\n",
    "        for x in arr1:\n",
    "            flag = 0\n",
    "            for y in arr2:\n",
    "                if abs(x-y) <= d:\n",
    "                    flag = 1\n",
    "                    break\n",
    "            if not flag:\n",
    "                res +=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1, arr2, d):\n",
    "      \n",
    "        res = 0\n",
    " \n",
    "        for num1 in arr1:\n",
    "            flag = 1\n",
    "            for num2 in arr2:\n",
    "                if abs(num1 - num2) <= d:\n",
    "                    flag = 0\n",
    "                    break\n",
    "            if flag:\n",
    "                res += 1\n",
    " \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        ans = 0\n",
    "        for i in arr1:\n",
    "            flag = 1\n",
    "            for j in arr2:\n",
    "                if abs(i-j) <= d:\n",
    "                    flag = 0\n",
    "                    break\n",
    "            if flag == 1:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        arr2.sort()\n",
    "        count = 0\n",
    "        for i in arr1:\n",
    "            p = bisect.bisect_left(arr2,i)\n",
    "            if p==len(arr2) or abs(i-arr2[p])>d:\n",
    "                if p==0 or abs(i-arr2[p-1])>d:\n",
    "                    count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        \n",
    "        cnt_value = 0\n",
    "        for ii in range(len(arr1)):\n",
    "            flag = True\n",
    "\n",
    "            for jj in range(len(arr2)):\n",
    "                if abs(arr1[ii] - arr2[jj]) <= d:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                cnt_value += 1\n",
    "        \n",
    "        return cnt_value\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        arr2.sort()\n",
    "        res = 0\n",
    "        for num in arr1:  # arr2中没有元素在[num - d, num + d]\n",
    "            i, j = 0, len(arr2)\n",
    "            while i < j:\n",
    "                mid = (i + j) // 2\n",
    "                if arr2[mid] >= num - d and arr2[mid] <= num + d:\n",
    "                    res += 1\n",
    "                    break\n",
    "                elif arr2[mid] < num - d:\n",
    "                    i = mid + 1\n",
    "                else:\n",
    "                    j = mid\n",
    "        return len(arr1) - res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        def binary_large(nums, target):\n",
    "            left = 0\n",
    "            right = len(nums) - 1\n",
    "            while left < right:\n",
    "                mid = (left + right)//2\n",
    "                if nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "        \n",
    "        def binary_small(nums, target):\n",
    "            left = 0\n",
    "            right = len(nums) - 1\n",
    "            while left < right:\n",
    "                mid = (left + right + 1)//2\n",
    "                if nums[mid] <= target:\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return left   \n",
    "        arr2.sort()\n",
    "        ans = 0\n",
    "        for i in arr1:\n",
    "            #print(i)\n",
    "            #print(binary_large(arr2, i), binary_small(arr2, i))\n",
    "            if abs(arr2[binary_large(arr2, i)] - i) > d and abs(i - arr2[binary_small(arr2, i)]) > d:\n",
    "                ans = ans + 1\n",
    "        return ans\n",
    "        #return  arr2[binary_large(arr2, arr1[0])], arr2[binary_small(arr2, arr1[0])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        arr2.sort()\n",
    "        res = 0\n",
    "        for element in arr1:\n",
    "            left =  bisect.bisect_left(arr2, element - d)\n",
    "            right = bisect.bisect_right(arr2, element + d)\n",
    "            if left == right: res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        x = len(arr1)\n",
    "        for i in arr1:\n",
    "            for j in arr2:\n",
    "                if abs(i-j) <= d:\n",
    "                    x -= 1\n",
    "                    break\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        s = set(arr2)\n",
    "        k = 0\n",
    "        for y in arr1:\n",
    "            a = y - d\n",
    "            b = y + d\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            r = True\n",
    "            for i in range(a, b + 1):\n",
    "                if i in s:\n",
    "                    r = False\n",
    "                    break\n",
    "            if r:\n",
    "                k += 1\n",
    "        return k \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        cnt = 0\n",
    "        for x in arr1:\n",
    "            flag = 0\n",
    "            for y in arr2:\n",
    "                if abs(x - y) <= d:\n",
    "                    flag = 1\n",
    "                    break\n",
    "            if flag == 0:\n",
    "                cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        arr2.sort()\n",
    "        k = 0\n",
    "        for i in arr1:\n",
    "            start = 0\n",
    "            end = len(arr2) - 1\n",
    "            mid = (start + end) >> 1\n",
    "            while start <= end:\n",
    "                if arr2[mid] < i:\n",
    "                    start = mid + 1\n",
    "                else:\n",
    "                    end = mid - 1\n",
    "                mid = (start + end) >> 1\n",
    "            if start == 0:\n",
    "                if abs(i - arr2[start]) > d:\n",
    "                    k += 1\n",
    "            elif start == len(arr2):\n",
    "                if abs(i - arr2[-1]) > d:\n",
    "                    k += 1\n",
    "            else:\n",
    "                if abs(i - arr2[start]) > d and abs(i - arr2[start - 1]) > d:\n",
    "                    k += 1\n",
    "        return k\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        ans = 0\n",
    "        for x in arr1:\n",
    "            ok = True\n",
    "            for y in arr2:\n",
    "                if abs(x - y) <= d:\n",
    "                    ok = False\n",
    "                    break\n",
    "            if not ok:\n",
    "                continue\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(arr1)):\n",
    "            for j in range(len(arr2)):\n",
    "                if abs(arr1[i] - arr2[j]) <= d:\n",
    "                    break\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:      \n",
    "        cnt=0\n",
    "        for i in range(len(arr1)):\n",
    "            flag1 = False\n",
    "            for j in range(len(arr2)):\n",
    "                if abs(arr1[i]-arr2[j]) >d:\n",
    "                    flag1=True\n",
    "                else:\n",
    "                    flag1=False\n",
    "                    break\n",
    "            if flag1==True:\n",
    "                cnt+=1\n",
    "        return  cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:\n",
    "        num1=0\n",
    "        for i in range(len(arr1)):\n",
    "            check=0\n",
    "            for j in range(len(arr2)):\n",
    "                if abs(arr1[i]-arr2[j]) <= d:\n",
    "                    check=1\n",
    "            if check == 0:\n",
    "                num1+=1\n",
    "        return num1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
